There are 6 people in a room. Each pair of people either mutually know each other or not. Prove that there are at least three people, who either all know each other, or none of whom know each other.
Answer: Lets connect two people by a red line if they know each other and blue line otherwise. Consider any person A. A has either 3 or more red lines going out, or 3 or more blue. Without loss of generality, lets say A has 3 red lines connecting to C, D, F (any three people). If C, D, F triangle has any red lines in it (say C-D), then A, C, D forms a red triangle, hence solved. If C, D, F has no red lines, then it is a blue triangle, hence solved. Same logic applies to 3 blue lines going out of A.